package me.test;

public class PascalTriangle2 {
    // 杨辉三角（递归实现）
    // 优化，降低时间复杂度,使用二维数组记忆法
    // 1.计算数字
    private static int element2(int[][] triangle, int i, int j) {
        // 已经在二维数组中，不用再重复计算
        if (triangle[i][j] > 0) {
            return triangle[i][j];
        }
        if (i == j || j == 0) {
            return 1;
        }
        triangle[i][j] = element2(triangle, i - 1, j - 1) + element2(triangle, i - 1, j);
        return triangle[i][j];
    }

    // 2.打印空格
    private static void printSpace(int n, int i) {
        int num = (n - 1 - i) * 2;
        for (int j = 0; j < num; j++) {
            System.out.print(" ");
        }
    }

    // 3.打印图形
    public static void print2(int n) {
        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) {
            // 创建代表列的数组
            triangle[i] = new int[i + 1];
            printSpace(n, i);
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", element2(triangle,i, j));
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        print2(5);
    }
}
